package finc_single_num;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class FindSingleNumPair {
    public static void main(String[] args) {
        /*
        假设一个集合中，所有的数都是成对出现，只有2个数是1个，找出这两个数
         */
        int[] nums = new int[]{1,2,1,3,2,5};

        /*int[] ints = m1(nums);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }*/
        int[] ints = m2(nums);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }

    public static int[] m1(int[] nums) {
        int bitmask = 0;
        for (int num : nums) bitmask ^= num;

        // rightmost 1-bit diff between x and y
        int diff = bitmask & (-bitmask);

        int x = 0;
        // bitmask which will contain only x
        for (int num : nums) if ((num & diff) != 0) x ^= num;
        int y = x ^ bitmask;
        return new int[]{x,y};
    }

    public static int[] m2(int[] nums) {
        Set<Integer> dup = new HashSet<>();
        for (int num : nums) if (!dup.add(num)) dup.remove(num);
        Iterator<Integer> iterator = dup.iterator();
        return new int[]{iterator.next(), iterator.next()};
    }
}
